COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\beginsubSection{Computing the Class Precedence List}
C00013 ENDMK
C⊗;
\beginsubSection{Computing the Class Precedence List}

The class lattice imposes a partial order on the classes in the lattice,
called the lattice order; this partial order is that a class {\bit
precedes} its direct superclasses.  This partial order will be represented
as a set of ordered pairs of classes called $R↓{\hbox{lattice}}$ where
$$R↓{\hbox{lattice}=\{(C↓1,C↓2)|\hbox{$C↓2$ is a direct superclass of
$C↓1$}\}$$ The {\bf DEFCLASS} form for each class provides a second
partial order, called the local precedence order; the local precedence
order is an ordered list of direct superclasses of a class.  This partial
order will be represented as a set of ordered pairs of classes called
$R↓{\hbox{lpo}}$; for every class C, if the local precedence order for
that class is $(C↓1\ldots C↓n)$, then $(C↓i,C↓{i+1})εR↓{\hbox{lpo}}$ for
$1≤i<n$.

We define a set called $R=R↓{\hbox{lattice}}∪R↓{\hbox{lpo}}$. $R$ may or may
not be a partial order depending on whether $R↓{\hbox{lattice}}$ and
$R↓{\hbox{lpo}}$ are consistent; we assume they are consistent and that
$R$ is a partial order. When $(C↓1,C↓2)εR$ we say that $C↓1$ {\bit precedes}
$C↓2$.

Let CL be the set of classes at or above C;
let $R'$ be the subset of $R$ where $R'=\{(C,D)|CεCL \hbox{and} DεCL\}$.
That is, $R'$ contains the pairs that involve the classes in CL.
To compute the class
precedence list at C, we topologically sort the elements of CL with
respect to the partial order, $R'$, and when the topological sort would
non-deterministically select a class from a set of equally good ones with
respect to $R'$, the class that appears first in a preorder treewalk is
selected.

\beginsubsubsection{Topological Sorting}

Topological sorting proceeds by finding a class C in~CL such that no other
class precedes that element according to the elements in~$R'$. C
is placed first in the result. We remove C from CL, and we remove all
relations of the form $(C,D)$, $DεCL$, from $R'$. We repeat the process, adding
classes with no predecessors at the end of the result. We stop when no
element can be found that has no predecessor.

If CL is not empty and the process has stopped, the order $R$ is
inconsistent:  if every class in the finite set of classes
is preceded by another,
then the relation contains a loop, and there are two classes, $C↓1$ and $C↓2$
such that $C↓1$ precedes $C↓2$ and $C↓2$ precedes $C↓1$.

Sometimes there are several classes from CL with no predecessors, and in
this case we select the one that appears first in a preorder treewalk
starting at C.

A preorder treewalk is defined in terms of the order in which classes are
{\bit visited} while performing a process of visiting classes called
``walking from a class.''  The following is a recursive definition of
walking from a class.  Let $C$ be a class and let $\{C↓1\ldots C↓n\}$ be
its direct superclasses in the local precedence order.  Nodes are visited
unless they have already been visited.  To walk from $C$, first $C$ is
visited, then we walk from $C↓1$, then we walk from $C↓2$, and so on until
we finally walk from $C↓n$.

\endsubsubsection%{Topological Sorting}

We require that an implementation of \CLOS\ signal an error if the
partial order is inconsistent.

\endsubSection%{Computing the Class Precedence List}

\beginsubSection{Example}

Here is an example of determining a class precedence list.  The classes
are defined:

(defclass pie (apple cinnamon) ())

(defclass apple (fruit) ())

(defclass cinnamon (spice) ())

(defclass fruit (food) ())

(defclass spice (food) ())

(defclass food () ())

The set CL~$=$ $\{$pie apple cinnamon fruit spice food$\}$. The set 
$R'$~$=$ $\{$(pie,apple) (pie,cinnamon) (apple,cinnamon) (apple,fruit) 
(cinnamon,spice) (fruit,food) (spice,food)$\}$.

PIE is not preceded by anything, so it comes first;
the result  so far is (PIE).
We remove
PIE from CL and relations mentioning PIE from $R'$ and get
CL~$=$ $\{$apple cinnamon fruit spice food$\}$ and
$R'$~$=$ $\{$(apple,cinnamon) (apple,fruit) (cinnamon,spice) (fruit,food)
(spice,food)$\}$.

APPLE is not preceded by anything, so it is next; the result is
(PIE APPLE). Removing APPLE and the relevant relations we get
CL~$=$ $\{$cinnamon fruit spice food$\}$ and
$R'$~$=$ $\{$(cinnamon,spice) (fruit,food) (spice,food)$\}$.

CINNAMON and FRUIT are not preceded by anything, so we look at which
of these two comes first in the preorder treewalk. The preorder
treewalk visits classes in this order:
PIE, APPLE, FRUIT, FOOD, CINNAMON, SPICE.
Therefore we select FRUIT next, and the result so far is
(PIE APPLE FRUIT).
CL~$=$ $\{$cinnamon spice food$\}$;
$R'$~$=$ $\{$(cinnamon,spice) (spice,food)$\}$.

CINNAMON is next, giving the result so far as (PIE APPLE FRUIT CINNAMON).
CL~$=$ $\{$spice food$\}$;
$R'$~$=$ $\{$(spice,food)$\}$.

SPICE and FOOD are added in that order, and the class precedence list
is (PIE APPLE FRUIT CINNAMON SPICE FOOD). 

\endsubSection%{Example}

\beginsubSection{Conflicting Class Definitions}

It is possible to write a set of class definitions that cannot be 
ordered.   For example: 

(defclass new-class (fruit apple) ())

(defclass apple (fruit) ())

FRUIT must precede APPLE because the local ordering of superclasses is
preserved.  APPLE must precede FRUIT because a class always precedes its
own superclasses.  When this situation occurs, an error is signalled
when the system tries to compute the class precedence list.

Note the following example, which appears at first glance to be a
conflicting set of definitions: 

(defclass pie (apple cinnamon) ())

(defclass pastry (cinnamon apple) ())

The ordering for PIE is:  (PIE APPLE CINNAMON)	

The ordering for PASTRY is:  (PASTRY CINNAMON APPLE)

There is no problem with the fact that APPLE precedes CINNAMON in the
ordering of the superclasses of PIE, but not in the ordering for PASTRY.
However, it is not possible to build a new class that has both PIE and
PASTRY as superclasses.

\endsubSection%{Conflicting Class Definitions}

\endSection%{Determining the Class Precedence List}